class Solution
{
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target)
    {
        if (source == target) return 0;
        int ans = 0x3f3f3f3f;
        unordered_map<int, vector<int>> hash;

        int n = routes.size();
        for (int i = 0; i < n; i++) for (auto& e : routes[i]) hash[e].push_back(i);

        if ((hash.find(source) == hash.end()) || (hash.find(target) == hash.end())) return -1;

        queue<pair<int, int>> q;
        unordered_map<int, bool> st, hsstop;
        q.push({ source,0 });
        while (!q.empty())
        {
            pair<int, int> p = q.front();
            q.pop();
            int s = p.first, dis = p.second;

            if (s == target)
            {
                ans = dis;
                break;
            }

            for (auto& a : hash[s])
            {
                if (st.find(a) != st.end() && st[a]) continue;
                for (auto& e : routes[a])
                {
                    if (hsstop.find(e) != hsstop.end() && hsstop[e]) continue;

                    hsstop[e] = true;
                    q.push({ e, dis + 1 });
                }
                st[a] = true;
            }


        }

        return ans == 0x3f3f3f3f ? -1 : ans;
    }
};